﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LemonKnapsack01
{
    public class Knapsack01Optimized
    {
        /// <summary>
        /// 空间优化版本 - 使用一维数组
        /// </summary>
        public static int SolveOptimized(int capacity, int[] weights, int[] values)
        {
            int n = weights.Length;

            // dp[j] 表示容量j下的最大价值
            int[] dp = new int[capacity + 1];

            // 初始化：容量0时价值为0
            for (int j = 0; j <= capacity; j++)
            {
                dp[j] = 0;
            }

            // 动态规划过程
            for (int i = 0; i < n; i++)
            {
                // 注意：必须从后往前遍历，避免重复选择
                for (int j = capacity; j >= weights[i]; j--)
                {
                    dp[j] = Math.Max(
                        dp[j],
                        dp[j - weights[i]] + values[i]
                    );
                }
            }

            return dp[capacity];
        }
    }
}
